import sys, time, BB
from Location import Location#, TIME_MAT
from consts import *

PICKUP = 'PICKUP'
ACTIVE_DROPOFF = 'Active DROPOFF'

PHP_ID = 0
PHP_ASSOC_ID = 1
SIZE = 2
WAIT = 3
EDGES = -1

id_map = {None:None}	# php_id -> loc_id
aggregated = []	# list of locations which are contained in an aggregate
PHP_TIME_MAT = {}

debug_route = []
locations = []



"""
Enable debug modes: options -D, -t

-D : Full debug mode with verbose debugging output and run timing. The 
next argument after the option is the desired route order to examine and 
compute the total wait time for. Formatted as: php_id_1,php_id_2,...,php_id_N

-t : Run timing results only. No other detail debugging info is provided.   

"""
def processDebug():
	global debug_route
	global DEBUG
	global TIMING

	if '-D' in sys.argv:
		DEBUG = True
		#BB.DEBUG = True
		TIMING = True
		idx = sys.argv.index("-D")
		if idx+1 < len(sys.argv) and ';' not in sys.argv[idx+1]:
			debug_route = sys.argv.pop(idx+1).split(',')
		sys.argv.pop(idx)

	if '-t' in sys.argv:
		TIMING = True
		idx = sys.argv.index("-t")
		sys.argv.pop(idx)




"""
Arg Format:
van;None;van_size;total_wait_passengers;x=time_a,...,time_N
id;assoc_id;size;current_wait;x=time_a,y=time_b,z=time_c,...,time_N

"""
def processArgs():
	global id_map
	global locations

	for loc in sys.argv[1:]:
		loc_args = loc.split(';')
		if loc_args[PHP_ASSOC_ID] in ['None','null']: # assoc_id
			loc_args[PHP_ASSOC_ID] = None
		
		new_loc = Location(loc_args[PHP_ID], loc_args[PHP_ASSOC_ID], int(loc_args[SIZE]), float(loc_args[WAIT]))
		locations.append(new_loc)

		id_map[loc_args[PHP_ID]] = new_loc.getID()
		BB.TIME_MAT[new_loc.getID()] = {}
				
	for loc in locations:
		loc.setAssocID(id_map[loc.getPHPAssocID()])

	for loc in sys.argv[1:]:
		for time in loc.split(';')[EDGES].split(','):
			BB.TIME_MAT[id_map[loc.split(';')[0]]][id_map[time.split('=')[0]]] = float(time.split('=')[1])



"""
Arg Format:
van;None;van_size;total_wait_passengers;x=time_a,...,time_N
id;assoc_id;size;current_wait;x=time_a,y=time_b,z=time_c,...,time_N

"""
def parseStrLoc(strloc):
	data = strloc.split(';')
	if data[PHP_ASSOC_ID] in ['None','null']:
		data[PHP_ASSOC_ID] = None
	return (data[PHP_ID], data[PHP_ASSOC_ID], int(data[SIZE]), float(data[WAIT]), data[EDGES])

def distance(strloc1, strloc2):
	php_id_loc1 = strloc1.split(';')[PHP_ID]
	php_id_loc2 = strloc2.split(';')[PHP_ID]
	return PHP_TIME_MAT[php_id_loc1][php_id_loc2]

def isMatch(strloc1, strloc2):
	php_id_loc1 = strloc1.split(';')[PHP_ID]
	php_id_loc2 = strloc2.split(';')[PHP_ID]
	return distance(strloc1,strloc2) == 0 and php_id_loc1 != php_id_loc2

def isCountablePickup(strloc):
	data = strloc.split(';')
	return int(data[SIZE]) > 0 and data[PHP_ASSOC_ID] in ['None','null']

def isUncountablePickup(strloc):
	data = strloc.split(';')
	return int(data[SIZE]) > 0 and data[PHP_ASSOC_ID] not in ['None','null']

def isActiveDropoff(strloc):
	data = strloc.split(';')
	return int(data[SIZE]) < 0 and data[PHP_ASSOC_ID] in ['None','null']

def isForbiddenDropoff(strloc):
	data = strloc.split(';')
	return int(data[SIZE]) < 0 and data[PHP_ASSOC_ID] not in ['None','null']

"""
Construct travel time matrix keyed on aggregate location ids.

This BB.TIME_MAT is used to access distances when computing the route.
It is not used outside of the BB module.

"""
def initBBTimeMat():
	for loc in aggregated:
		BB.TIME_MAT[loc.getID()] = {}

	# Finish setting up BB.TIME_MAT for BB.py
	for loc in sys.argv[1:]:
		for time in loc.split(';')[EDGES].split(','):
			BB.TIME_MAT[id_map[loc.split(';')[0]]][id_map[time.split('=')[0]]] = float(time.split('=')[1])

"""
Construct travel time matrix keyed on php_ids.

This PHP_TIME_MAT is only used to identify duplicate/identical locations
for constructing aggregate locations.

"""
def initPHPTimeMat():
	global PHP_TIME_MAT

	locations = sys.argv[1:]
	for loc in locations:
		fields = loc.split(';')
		
		PHP_TIME_MAT[fields[PHP_ID]] = {}

		edges = fields[EDGES].split(',')
		for edge in edges:
			dest_id = edge.split('=')[0]	# destination php_id
			time = float(edge.split('=')[1])	# time to travel to destination
			PHP_TIME_MAT[fields[PHP_ID]][dest_id] = time

"""
Verify that the total size of all requests is non-negative.

If the total size is negative, set errcd = -1 indicating invalid size.
Return errcd to indicate whether or not the input is valid.

"""
def validate():
	global errcd
	if sum([loc.getSize() for loc in aggregated]) < 0:
		errcd = ENEGSIZE
	return errcd

"""
Aggregate the locations given in locations.

This function should only ever be applied to lists of PICKUPs or lists
of Active DROPOFFs; never to any other kind of list.

Precondition: 
Every location contained in locations must be of the same type (eg: 
Active DROPOFF). Furthermore, only three location types may be contained 
in locations: Countable PICKUP (has no associated DROPOFF), Uncountable 
PICKUP (has associated DROPOFF), and Active DROPOFF (has no associated 
PICKUP). So the only three cases are as follows: case1 is every location 
in locations is a Countable PICKUP, case2 is every location in locations 
is an Uncountable PICKUP, and case3 is every location in locations is an 
Active DROPOFF.

"""
def aggregateLocType(locations):
	global aggregated

	while len(locations) > 0:
		# aggregate everything matching the first remaining location
		loc = locations[0]
		
		# Set up for aggregation of locations matching loc
		loc_data = parseStrLoc(loc)
		# initialize the aggregation variables to data for loc
		agg_php_id = [loc_data[PHP_ID]]
		agg_php_assoc_id = [loc_data[PHP_ASSOC_ID]]
		agg_size = int(loc_data[SIZE])
		agg_wait = float(loc_data[WAIT])
		# remove loc from future consideration
		locations.pop(0)
		
		# Perform aggregation with any matching locations.
		# check all remaining locations from last to first. (allows us to remove matches during loop w/o indexing errors)
		for i in range(len(locations)-1, -1, -1):
			other = locations[i]
			if isMatch(loc, other):
				other_data = parseStrLoc(other)

				# prevent making an aggregate location which is too big
				if agg_size + int(other_data[SIZE]) > 10:
					break

				# incorportate match into aggregation variables
				agg_php_id += [other_data[PHP_ID]]
				agg_php_assoc_id += [other_data[PHP_ASSOC_ID]]
				agg_size += int(other_data[SIZE])
				agg_wait += float(other_data[WAIT])

				# remove match from future consideration
				locations.pop(i)

		# Finished aggregation process for locations matching loc.
		# Create single aggregate Location object for loc matches.
		# Let associated location be default value None since the 
		# id mapping is incomplete until all dropoffs have been 
		# handled so we can't set it yet.
		new_loc = Location(agg_php_id, agg_php_assoc_id, agg_size, agg_wait)

		# associate php_ids with their aggregate location object
		for php_id in agg_php_id:
			id_map[php_id] = new_loc.getID()

		#BB.TIME_MAT[new_loc.getID()] = {}

		aggregated.append(new_loc)

		'''
		matches = [other for other in pickups if isMatch(loc, other)]
		pickups = [other for other in pickups if not isMatch(loc, other)]
		for match in matches:
			data = parseStrLoc(match)
			agg_size += data[SIZE]
			agg_wait += data[WAIT]
			agg_php_id += [data[PHP_ID]]
			agg_php_assoc_id += [data[PHP_ASSOC_ID]]
		'''

"""
Perform location aggregation when possible. (Must be same real world location)

PICKUPs can be aggregated.
Active DROPOFFs (no assoc_id) can be aggregated.

"""
def aggregateLocs():
	global aggregated

	# van isn't aggregated so create "aggregate" form location object separately.
	van = sys.argv[1]
	van_data = parseStrLoc(van)
	van_loc = Location([van_data[PHP_ID]], [van_data[PHP_ASSOC_ID]], van_data[SIZE], van_data[WAIT])
	id_map[van_data[PHP_ID]] = van_loc.getID()
	#BB.TIME_MAT[van_loc.getID()] = {}
	aggregated.append(van_loc)

	# skip the van location when aggregating
	locations = sys.argv[2:]
	
	# group the PICKUPs because they can be aggregated together
	# group the Active DROPOFFs because they can be aggregated together
	# group the Forbidden DROPOFFs because they all remain unaggregated
	countable_pickups = [loc for loc in locations if isCountablePickup(loc)]
	uncountable_pickups = [loc for loc in locations if isUncountablePickup(loc)]
	active_dropoffs = [loc for loc in locations if isActiveDropoff(loc)]
	forbidden_dropoffs = [loc for loc in locations if isForbiddenDropoff(loc)]	
	
	# Run through pickups one by one.
	# For each remaining PICKUP, aggregate it with any matching remaining
	# and then remove all of these from future consideration.
	aggregateLocType(countable_pickups)
	aggregateLocType(uncountable_pickups)
	# Run through Active DROPOFFs one by one.
	# For each remaining Active DROPOFF, aggregate it with any matching
	# remaining and then remove all of these from future consideration.
	aggregateLocType(active_dropoffs)

	# Run through each forbidden_dropoff.
	# These cannot be aggregated so we simply construct a new "aggregate"
	# location (php_id, php_assoc_id as lists not strings) for each one.
	for loc in forbidden_dropoffs:
		loc_data = parseStrLoc(loc)
		
		agg_php_id = [loc_data[PHP_ID]]
		agg_php_assoc_id = [loc_data[PHP_ASSOC_ID]]
		agg_size = int(loc_data[SIZE])
		agg_wait = float(loc_data[WAIT])

		# the assoc loc for a DROPOFF is always a PICKUP and we already 
		# aggregated all the PICKUPs so the php_assoc_id is guarenteed 
		# to have already been mapped so we can use the map here.
		agg_assoc_id = id_map[loc_data[PHP_ASSOC_ID]]	

		new_loc = Location(agg_php_id, agg_php_assoc_id, agg_size, agg_wait, agg_assoc_id)
		id_map[loc_data[PHP_ID]] = new_loc.getID()
		#BB.TIME_MAT[new_loc.getID()] = {}

		aggregated.append(new_loc)

	# now that all dropoffs have been handled we go and set the assoc loc
	# for the pickup locations which need it for deciding isCountable().
	for loc in aggregated:
		if loc.getSize() > 0:
			loc.setAssocID(id_map[sorted(loc.getPHPAssocID())[-1]])

""" 
Sample Commands:
python routing.py 'Van;None;0;0;A=1,A2=1.4,B=2,B2=2.8' 'A;A2;1;0;Van=1,A2=1,B=1,B2=2.236' 'A2;A;-1;0;Van=1.4,A=1,B=1.4,B2=1.4' 'B;B2;1;0;Van=2,A=1,A2=1.4,B2=2' 'B2;B;-1;0;Van=2.8,A=2.236,A2=1.4,B=2'
python routing.py '0;None;0;0;0=0,1=12246,2=39725,3=122841,4=69504' '1;None;1;0;0=12454,1=0,2=35051,3=111440,4=74019' '2;None;1;0;0=40320,1=35344,2=0,3=99299,4=67513' '3;1;-1;0;0=123766,1=112004,2=99275,3=0,4=161908' '4;2;-1;0;0=67872,1=72553,2=65902,3=160969,4=0'

"""
def main():
	global locations

	processDebug()

	initPHPTimeMat()
	aggregateLocs()
	initBBTimeMat()

	validate()
	if errcd:
		print errcd
		sys.exit(errcd)

	start = time.clock()
	BB.optimizeRoute(aggregated)
	end = time.clock()

	BB.printRoute()

	if TIMING:
		print
		print "time:", end-start
		print

	if DEBUG:
		print "aggregated:"
		for loc in aggregated:
			print loc.id, loc.php_id, loc.php_assoc_id, loc.getAssocLoc()
		print



if __name__ == '__main__':
	main()
